package com.ds.seqlist.LeetCode;

public class Num142_DetectCycle {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head,low = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if (fast == low) {
                // 从相遇开始，从head开始引入一个新引用，这个新引用一定会和慢指针在环的入口相遇
                ListNode third = head;
                while (third != low) {
                    low = low.next;
                    third = third.next;
                }
                return low;
            }
        }
        return null;
    }
}
